TeX 1995 July

home *** CD-ROM | disk | FTP | other *** search

/ TeX 1995 July / TeX CD-ROM July 1995 (Disc 1)(Walnut Creek)(1995).ISO / macros / plain / contrib / tree.tex < prev next >

Wrap

Text File | 1992-08-26 | 11.5 KB | 309 lines

% Tree -- a macro to make aligned (horizontal) trees in TeX % % Input is of the form % \tree % item % \subtree % \leaf{item} % . % . % . % \endsubtree % \subtree % . % . % . % \endsubtree % \endsubtree % \endtree % % Nesting is to any level. \leaf is defined as a subtree of one item: % \def\leaf#1{\subtree#1\endsubtree}. % % A structure: % \subtree % item_part1 % item_part2 % . % . % . % % will print item_part2 directly below item_part1 as a single item % as if they were in a \box. % % The macro is a 3-pass macro. On the first pass it sets up a data % structure from the \subtree ... \endsubtree definitions. On the second pass % it recursively calculates the width of each level of the tree. On the third % pass it sets up the boxes, glue and rules. % % By David Eppstein, TUGboat, vol. 6 (1985), no. 1, pp. 31--35. % Transcribed by Margaret Kromer (peg), Feb., 1986. % % Pass 1 % At the end of pass 1, the tree is coded as a nested collection of \hboxes % and \vboxes. \newbox\treebox\newcount\treeboxcnt \def\tree{\message{Begin tree}\treeboxcnt=1\global\setbox\treebox=\boxtree} \def\subtree{\ettext \advance\treeboxcnt by 1 \boxtree} \def\leaf#1{\subtree#1\endsubtree} \def\endsubtree{\ettext \egroup \advance\treeboxcnt-1{}% \ifnum\treeboxcnt=-1 \treeerrora\fi} \def\endtree{\endsubtree \ifnum\treeboxcnt>0 \treeerrorb\fi% \settreesizes \typesettree \message{-- end tree}} % Error messages for unbalanced tree \def\treeerrora{\errhelp=\treeerrorahelp% \errmessage{Unbalanced tree -- too many endsubtrees}} \newhelp\treeerrorahelp{There are more subtrees closed than opened} \def\treeerrorb{\errhelp=\treeerrorbhelp% \errmessage{Unbalanced tree -- not enough endsubtrees}} \newhelp\treeerrorbhelp{Not all the subtrees of the tree are closed. If you continue, you'll get some mysterious secondary errors.} % Set up \vbox containing root of tree \newif\iftreetext\treetextfalse % Whether still aligning text \def\boxtree{\hbox\bgroup % Start outer box of tree or subtree \baselineskip 2.5ex % Narrow line spacing slightly \tabskip 0pt % No spurious glue in alignment \vbox\bgroup % Start inner text \vbox \treetexttrue % Remember for \ettext \let\par\crcr \obeylines % New line breaks without explicit \cr \halign\bgroup##\hfil\cr} % Start alignment with simple template \def\ettext{\iftreetext % Are we still in inner text \vbox? \crcr\egroup \egroup \fi} % Yes, end alignment and box % Pass 2 % Recursively calculate widths of tree with \setsizes; keep results in % \treesizes; \treewidth contains total width calculated so far. \treeworkbox % is workspace containing subtree being sized. \newbox\treeworkbox \def\cons#1#2{\edef#2{\xmark #1#2}} % Add something to start of list \def\car#1{\expandafter\docar#1\docar} % Take first element of list \def\docar\xmark#1\xmark#2\docar{#1} % ..by ignoring rest in expansion \def\cdr#1{\expandafter\docdr#1\docdr#1}% Similarly, drop first element \def\docdr\xmark#1\xmark#2\docdr#3{\def#3{\xmark #2}} \def\xmark{\noexpand\xmark} % List separator expands to self \def\nil{\xmark} % Empty list is just separator \def\settreesizes{\setbox\treeworkbox=\copy\treebox% \global\let\treesizes\nil \setsizes} \newdimen\treewidth % Width of this part of the tree \def\setsizes{\setbox\treeworkbox=\hbox\bgroup% Get a horiz list as a workspace \unhbox\treeworkbox\unskip % Take tree, unpack it into horiz list \inittreewidth % Get old width at this level \sizesubtrees % Recurse through all subtrees \sizelevel % Now set width from remaining \vbox \egroup} % All done, finish our \hbox \def\inittreewidth{\ifx\treesizes\nil % If this is the first at this level \treewidth=0pt % ..then we have no previous max width \else \treewidth=\car\treesizes % Otherwise take old max level width \global\cdr\treesizes % ..and advance level width storage \fi} % ..in preparation for next level. \def\sizesubtrees{\loop % For each box in horiz list (subtree) \setbox\treeworkbox=\lastbox \unskip % ..pull it off list and flush glue \ifhbox\treeworkbox \setsizes % If hbox, it's a subtree - recurse \repeat} % ..and loop; end loop on tree text \def\sizelevel{% \ifdim\treewidth<\wd\treeworkbox % If greater than previous maximum \treewidth=\wd\treeworkbox \fi % Then set max to new high \global\cons{\the\treewidth}\treesizes}% In either case, put back on list % Pass 3 % Recursively typeset tree with \maketree by adding an \hbox containing % a subtree (in \treebox) to the horizontal list. \newdimen\treeheight % Height of this part of the tree \newif\ifleaf % Tree has no subtrees (is a leaf) \newif\ifbotsub % Bottom subtree of parent \newif\iftopsub % Top subtree of parent \def\typesettree{\medskip\maketree\medskip} % Make whole tree \def\maketree{\hbox{\treewidth=\car\treesizes % Get width at this level \cdr\treesizes % Set up width list for recursion \makesubtreebox\unskip % Set \treebox to text, make subtrees \ifleaf \makeleaf % No subtrees, add glue \else \makeparent \fi}} % Have subtrees, stick them at right {\catcode`@=11 % Be able to use \voidb@x \gdef\makesubtreebox{\unhbox\treebox % Open up tree or subtree \unskip\global\setbox\treebox\lastbox % Pick up very last box \ifvbox\treebox % If we're already at the \vbox \global\leaftrue \let\next\relax % ..then this is a leaf \else \botsubtrue % Otherwise, we have subtrees \setbox\treeworkbox\box\voidb@x % Init stack of processed subs \botsubtrue \let\next\makesubtree % ..and call \maketree on them \fi \next}} % Finish up for whichever it was \def\makesubtree{\setbox1\maketree % Call \maketree on this subtree \unskip\global\setbox\treebox\lastbox % Pick up box before it \treeheight=\ht1 % Get height of subtree we made \advance\treeheight 2ex % Add some room around the edges \ifhbox\treebox \topsubfalse % If picked up box is a \vbox, \else \topsubtrue \fi % ..this is the top, otherwise not \addsubtreebox % Stack subtree with the rest \iftopsub \global\leaffalse % If top, remember not a leaf \let\next\relax \else % ..(after recursion), set return \botsubfalse \let\next\makesubtree % Otherwise, we have more subtrees \fi \next} % Do tail recursion or return \def\addsubtreebox{\setbox\treeworkbox=\vbox{\subtreebox\unvbox\treeworkbox}} \def\subtreebox{\hbox\bgroup % Start \hbox of tree and lines \vbox to \treeheight\bgroup % Start \vbox for vertical rules \ifbotsub \iftopsub \vfil % If both bottom and top subtree \hrule width 0.4pt % ..vertical rule is just a dot \else \treehalfrule \fi \vfil % Bottom gets half-height rule \else \iftopsub \vfil \treehalfrule % Top gets half-height the other way \else \hrule width 0.4pt height \treeheight \fi\fi % Middle, full height \egroup % Finish vertical rule \vbox \treectrbox{\hrule width 1em}\hskip 0.2em\treectrbox{\box1}\egroup} \def\treectrbox#1{\vbox to \treeheight{\vfil #1\vfil}} \def\treehalfrule{\dimen\treeworkbox=\treeheight % Get total height \divide\dimen\treeworkbox 2% \advance\dimen\treeworkbox 0.2pt % Divide by two, add half horiz height \hrule width 0.4pt height \dimen\treeworkbox}% Make a vertical rule that high \def\makeleaf{\box\treebox} % Add leaf box to horiz list \def\makeparent{\ifdim\ht\treebox>% \ht\treeworkbox % If text is higher than subtrees \treeheight=\ht\treebox % ..use that height \else \treeheight=\ht\treeworkbox \fi % Otherwise use height of subtrees \advance\treewidth-\wd\treebox % Take remainder of level width \advance\treewidth 1em % ..after accounting for text and glue \treectrbox{\box\treebox}\hskip 0.2em % Add text, space before connection \treectrbox{\hrule width \treewidth}% \treectrbox{\box\treeworkbox}} % Add \hrule, subs ************************************************ % Plain TeX driver for tree.tex \def\uncatcodespecials{\catcode`@=12\def\do##1{\catcode`##1=12}\dospecials} \def\setupverbatim{\tt\obeylines\uncatcodespecials\obeyspaces} {\obeyspaces\global\let =\ } \def\beginshowoff{\par\begingroup\setupverbatim\doverbatim} {\catcode`\!=0 \catcode`\\=12 !obeylines!gdef!doverbatim^^M#1\endshowoff{#1!endgroup!medbreak!filbreak% !smallskip}} % see The TeXbook, exercise 22.14 \input tree.tex \centerline{\bf TREE TREE} \bigskip \tree Tree Uses \subtree Computer Science \subtree Data Structures \leaf{Search Tree} \leaf{Priority Queue} \endsubtree \subtree Parsing \leaf{Parse Tree} \leaf{Symbol Table} \endsubtree \subtree Structured Programming \endsubtree \endsubtree \subtree Genealogy \leaf{Ancestors} \leaf{Descendants} \endsubtree \subtree Electrical Engineering \subtree Paper \leaf{{\it Vitae}} \leaf{Announcements} \leaf{Proposals} \leaf{\TeX{} Samples} \endsubtree \endsubtree \subtree Construction \leaf{Fences} \subtree Buildings \subtree Houses \leaf{Human} \leaf{Dog} \leaf{Bird} \leaf{Tree} \endsubtree \leaf{Barns} \leaf{Other} \endsubtree \leaf{\dots} \endsubtree \subtree Taxonomies \leaf{Tree Uses} \endsubtree \endtree \vskip.5truein \beginshowoff % see The TeXbook, exercise 22.14 \input tree.tex \centerline{TREE TREE} \bigskip \tree Tree Uses \subtree Computer Science \subtree Data Structures \leaf{Search Tree} \leaf{Priority Queue} \endsubtree \subtree Parsing \leaf{Parse Tree} \leaf{Symbol Table} \endsubtree \subtree Structured Programming \endsubtree \endsubtree \subtree Genealogy \leaf{Ancestors} \leaf{Descendants} \endsubtree \subtree Electrical Engineering \subtree Paper \leaf{{\it Vitae}} \leaf{Announcements} \leaf{Proposals} \leaf{\TeX{} Samples} \endsubtree \endsubtree \subtree Construction \leaf{Fences} \subtree Buildings \subtree Houses \leaf{Human} \leaf{Dog} \leaf{Bird} \leaf{Tree} \endsubtree \leaf{Barns} \leaf{Other} \endsubtree \leaf{\dots} \endsubtree \subtree Taxonomies \leaf{Tree Uses} \endsubtree \endtree \endshowoff \bye